5 链表反转【无头结点】

【题目描述】

题目：输入一个链表的头结点，反转该链表，并返回反转后链表的头结点。

typedef int data_t;

typedef struct linklist_node_t
{
    data_t data;
    struct linklist_node_t *next;
}linklist_t;

【分析与解法】

这是一道广为流传的微软面试题。由于这道题能够很好的反应出程序员思维是否严密，在微软之后已经有很多公司在面试时采用了这道题。

为了正确地反转一个链表，需要调整指针的指向。与指针操作相关代码总是容易出错的，因此最好在动手写程序之前作全面的分析。在面试的时候不急于动手而是一开始做仔细的分析和设计，将会给面试官留下很好的印象，因为在实际的软件开发中，设计的时间总是比写代码的时间长。与其很快地写出一段漏洞百出的代码，远不如用较多的时间写出一段健壮的代码。

下面我们用图进行描述。

使用p和q两个指针配合工作，使得两个节点间的指向反向，同时用r记录剩下的链表。

p = head;
q = head->next;

head->next = NULL;

现在进入循环体，这是第一次循环。

r = q->next;
q->next = p;

p = q;
q =r;

接下来就是依次进行循环。最后将原头节点的指针域指向原来最后一个元素节点。具体代码如下所示：

【方法一：逐链反转】

使用3个指针遍历单链表，逐个链接点进行反转。

linklist_t *linklist_reverse(linklist_t *head)
{
    linklist_t *p,*q,*r;

    if(head == NULL)
    {
        return NULL;
    }

    p = head;//保存第一个元素节点的位置
    q = head->next;

    head->next = NULL;//旧的头指针是新的尾指针，next需要指向NULL

    while(q)
    {
        r = q->next;
        q->next = p;
        p = q;
        q = r;
   }
   head = p;//原头节点的指针域指向原来最后一个元素节点
   return head;
}

【方法二：插入反转】

对于一条链表，从第2个节点到第N个节点，依次逐节点插入到第1个节点(head节点)之后，(N-1)次这样的操作结束之后将第1个节点挪到新表的表尾即可。

代码如下所示：

linklist_t *linklist_reverse(linklist_t *head)
{
    linklist_t *p,*q;

    if(head == NULL)
    {
        return NULL;
    }
    p = head->next;
    while(p->next != NULL)
    {
        q = p->next;
        p->next = q->next;
        q->next = head->next;
        head->next = q;
    }
    p->next=head;//相当于成环
    head=p->next->next;//新head变为原head的next
    p->next->next=NULL;//断掉环

    return head;
}

【方法三：递归】

因为发现大部分问题都可以从递归角度想想，所以这道题目也从递归角度想了想。

递归的方法其实是非常巧的，它利用递归走到链表的末端，然后再更新每一个node的next 值 ，实现链表的反转。而newhead 的值没有发生改变，为该链表的最后一个结点，所以，反转后，我们可以得到新链表的head。

现在需要把A->B->C->D进行反转，

可以先假设B->C->D已经反转好，已经成为了D->C->B,那么接下来要做的事情就是将D->C->B看成一个整体，让这个整体的next指向A，所以问题转化了反转B->C->D。那么，可以先假设C->D已经反转好，已经成为了D->C,那么接下来要做的事情就是将D->C看成一个整体，让这个整体的next指向B，所以问题转化了反转C->D。那么，

可以先假设D(其实是D->NULL)已经反转好，已经成为了D(其实是head->D),那么接下来要做的事情就是将D(其实是head->D)看成一个整体，让这个整体的next指向C，所以问题转化了反转D。

接下来就用图来表示反转步骤。

程序刚开始执行，if 语句失效，进入 else 语句，然后执行

Node *newhead = linklist_reverse(head->next);

第二个结点的指针参数传入递归函数，一直到，最后一个结点的指针参数传入递归函数，if 语句有效：

head-> next == NULL;

返回当前的head 给 newhead 指针指向，如图：

其实在递归函数栈内，按照后进先出的顺序，执行一级级的递归函数，返回末位结点给 newhead 之后，执行递归栈里的第二个递归函数，发生如图

返回 newhead，也就是新的反转之后的链表（临时的），然后进入到递归工作栈里的第一个递归函数，如图：

返回 newhead，也就是反转之后的链表，此时递归工作栈的函数全部执行，返回的结点就是反转之后的链表的头结点（之前的尾结点）。

代码如下所示：

linklist_t *linklist_reverse(linklist_t *head)
{
    //如果链表为空或者链表中只有一个元素
    if(head == NULL || head->next == NULL)
    {
        return head;
    }
    else
    {
        //先反转后面的链表，走到链表的末端结点
        linklist_t *newhead = linklist_reverse(head->next);
        //再将当前节点设置为后面节点的后续节点
        head->next->next = head;
        head->next = NULL;
        return newhead;
    }
}

【练一练】

[链表翻转]

给出一个链表和一个数k，比如，链表为1→2→3→4→5→6，k=2，则翻转后2→1→6→5→4→3，若k=3，翻转后3→2→1→6→5→4，若k=4，翻转后4→3→2→1→6→5，用程序实现。

【分析与解法】

这个就比较简单，可以参看上文的方法一，只是不反转整个链表，而是反转一部分，再将未反转的连接即可。

linklist_t *linklist_k_reverse(linklist_t *head,int k)
{
    int i;
    linklist_t *p,*q,*r;

    if(head == NULL)
    {
        return NULL;
    }
    q = head->next;
    p = head;//保存第一个元素节点的位置

    head->next = NULL;//旧的头指针是新的尾指针，next需要指向NULL

    for(i = 0;i < k-1;i++)
    {
        r = q->next;
        q->next = p;
        p = q;
        q = r;
    }

    //翻转的部分
    head = p;//原头节点的指针域指向原来最后一个元素节点

    linklist_t *t = head;
    //翻转的部分连接未反转的部分
    while(t->next)
    {
        t = t->next;
    }
    t->next = q;

    return head;
}

资源获取方法

1.关注公众号[嵌入式实验楼]
2.在公众号回复关键词[Data Structures and Algorithms]获取资料提取码